/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	Question1525
 * 模块说明：
 * 修改历史：
 * 2025/4/24 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;

/**
 * 给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ， 它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。请你返回 s
 * 中好分割的数目。
 * <p>
 * 示例1： 输入：s = "aacaba"
 * <p>
 * 输出：2
 * <p>
 * 解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
 * <p>
 * ("a", "acaba") 左边和右边分别包含 1 个和 3 个不同的字符。
 * <p>
 * ("aa", "caba") 左边和右边分别包含 1 个和 3 个不同的字符。
 * <p>
 * ("aac", "aba") 左边和右边分别包含 2 个和 2 个不同的字符。这是一个好分割。
 * <p>
 * ("aaca", "ba") 左边和右边分别包含 2 个和 2 个不同的字符。这是一个好分割。
 * <p>
 * ("aacab", "a") 左边和右边分别包含 3 个和 1 个不同的字符。
 * <p>
 * 示例2： 输入：s = "abcd"
 * <p>
 * 输出：1
 * <p>
 * 解释：好分割为将字符串分割成 ("ab", "cd") 。
 *
 * @author lizhixing
 */
public class Question1525 {


  public static void main(String[] args) {
    Question1525 question = new Question1525();
    String str = "aacaba";
    System.out.println(question.numSplits(str));
  }

  public int numSplits(String s) {
    int left = 0, ans = 0;
    int[] mp1 = new int[26];// 记录每个字符的个数。
    int[] mp2 = new int[26];
    int right = 0;// 总的字符数，相同的字符只能算一个。
    for (char ch : s.toCharArray()) {
      if (mp1[ch - 'a']++ == 0)
        right++;
    }

    for (char ch : s.toCharArray()) {
      if (mp2[ch - 'a']++ == 0)// 出现一个新字符
        left++;
      if (--mp1[ch - 'a'] == 0)// 消失一个字符。
        right--;
      if (left == right)// 左边的和右边的字符一样
        ans++;
    }
    return ans;
  }


}
